%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Report for the DRIDE projet, an image database exploration projet developped
% at Télécom Paristech
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Created by Olivier Le Floch on 2008-08-31.
% Last updated by Olivier Le Floch on 2008-09-01.
% Copyright (c) 2007-2008. All rights reserved.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\documentclass[a4paper,11pt,twoside]{article}

% Use utf-8 encoding for foreign characters
\usepackage[utf8]{inputenc}
\usepackage[francais, english]{babel}

% Setup for fullpage use
\usepackage{fullpage}

% Package for including code in the document
\usepackage{listings}
\usepackage[usenames]{color}

\usepackage{amsfonts}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{latexsym}
\usepackage{pdfsync}
\usepackage{floatflt}
\usepackage{url}
\usepackage[pdftex]{graphicx}

% Code Formating
\usepackage{listings}
\lstloadlanguages{Python, SQL}
\newcommand{\preparePython}{\lstset{language=Python}}
\newcommand{\prepareSQL}{\lstset{language=SQL}}
\preparePython

\definecolor{lbcolor}{rgb}{0.9,0.9,0.9}
\lstset{
  basicstyle=\small\ttfamily,
  float=t,frame=tb,backgroundcolor=\color{lbcolor},rulecolor=\color{black},
  framexleftmargin=5pt,tabsize=4,showstringspaces=false,
  numbers=left,stepnumber=5,numberstyle=\tiny,
  numbersep=5pt,numberfirstline=true,numberblanklines=true,
  commentstyle=\itshape\color{Gray},keywordstyle=\color{blue}\bfseries,
  stringstyle=\color{red},emph={\%inf,\%T,\%F},
  emphstyle=\color{OliveGreen}\bfseries,
  literate={<>}{$\neq$}1 {!=}{$\neq$}1 {<=}{$\le$}1 {>=}{$\ge$}1}

\newcommand{\code}[1]{\texttt{#1}}

\NoAutoSpaceBeforeFDP
\AddThinSpaceBeforeFootnotes
\FrenchFootnotes
\DeclareGraphicsRule{.tif}{png}{.png}
  {`convert #1 `dirname #1`/`basename #1 .tif`.png}

\usepackage[nottoc]{tocbibind}
\setcounter{tocdepth}{2}

% définitions de symboles mathématiques
% ensemble des réels
\newcommand{\R}{\mathbb{R}}
% ensemble des entiers naturels
\newcommand{\N}{\mathbb{N}}
% d droit (pour les éléments différentiels)
\newcommand{\ud}{\, \mathrm{d}} 
\DeclareMathOperator{\Noise}{Noise}
\providecommand{\abs}[1]{\lvert#1\rvert}
\providecommand{\floor}[1]{\lfloor#1\rfloor}
\providecommand{\ceil}[1]{\lceil#1\rceil}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% START OF REPORT                                                            %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\title{
\vspace{-3cm}
\normalsize
\begin{tabular}{p{15cm}}
TÉLÉCOM Paristech \\
LE FLOCH Olivier
\end{tabular}
\vspace{6cm}
\large
\begin{center}
RAPPORT DE DOUBLE BRIQUE DE PROJET\\
\vspace{1cm}
{\Huge DRIDE\\
\vspace{1cm}
Dimensionality reduction\\
\& Image database exploration}\\
\end{center}
\vspace{6cm}
}
\author{}
\date{}

\begin{document}

\DeclareGraphicsExtensions{.pdf, .jpg, .tif}
\selectlanguage{english}

\thispagestyle{empty}
\maketitle

\clearpage \section*{}
\markboth{Abstract}{}

\selectlanguage{english}

\textbf{Abstract}

La recherche d’images dans une base de données se fait généralement par
l’intermédiaire de requêtes textuelles basées sur des données textuelles de
contexte. Par ailleurs, il n’existe pour l’instant pas de bons outils de
visualisation d’une banque d’images dans son ensemble. Lorsque l’on explore
une collection de photos, elles sont affichées par ordre d’ajout sous forme
d’une liste de vignettes, sans indication des images visuellement similaires.

Nous proposons d’explorer les techniques de recherche basées sur le contenu
afin d’améliorer les techniques d’extraction de caractéristiques des images,
les méthodes d’obtention d’une représentation spatiale des images prenant en
compte les informations de requêtes d’intérêt ainsi que le contenu des images,
et enfin les interfaces de visualisation des représentations spatiales
d’images.

Nous présentons ici un schéma architectural pour une plate-forme d'exploration
de base de données d'images innovante se basant sur une visualisation
hiérarchique d'une représentation multi-dimensionnelle des images localisées
par proximité de features locaux. Nous présentons des implémentations simples
des principaux composants de cette architecture afin d'en montrer la
faisabilité.

\clearpage \thispagestyle{plain}
\tableofcontents

\clearpage
\section*{Introduction}
\addcontentsline{toc}{section}{Introduction}
\markboth{Introduction}{}

Ce projet vise à fournir des outils d’exploration de banques d’images
innovants permettant de visualiser aisément l’ensemble d’une base de données
d’images. Nous souhaitons développer des algorithmes génériques capables
d’opérer sur des bases d’images dont le contenu peut ou non être spécialisé
(images satellitaires, photographies, illustrations, logos, base hétéroclite),
et permettant d’obtenir une représentation spatiale multidimensionnelle des
images dans laquelle la proximité de deux images reflète la proximité
ressentie par un utilisateur et la vérité terrain représentée par l'image, qui
n’est pas nécessairement disponible. Nous présentons l'architecture d'une
interface d’exploration de banque d’images basée sur les informations de
proximité précédentes et permettant des interactions riches, en particulier
pour spécifier des requêtes d’intérêt, de filtrage ou de navigation spatiale
en explorant les possibilités d’animation peu exploitées jusqu’ici, ainsi
qu’une approche par requêtes exploratoires.

Nous présenterons tout d'abord l'état de l'art de la recherche d'images basée
sur le contenu, puis les aspects théoriques derrière la solution exploratoire
retenue pour DRIDE. Nous décrirons ensuite l'architecture proposée et les
choix techniques retenus, ainsi que le fonctionnement des outils développés
dans le cadre du projet pour démontrer la faisabilité de celle-ci. Enfin, nous
présenterons les évolutions qui pourront être envisagées pour ce projet.

\begin{figure}[h]
  \centering
    \includegraphics[width=15truecm]{figures/introduction.png}
  \caption
    {Exemple de visualisation fournie par DRIDE}
\end{figure}

\clearpage
\section{État de l'art}

Dans cette section nous allons essayer d'expliciter le problème que nous
tentons de résoudre en résumant l'état de l'art actuel dans l'exploration et
la recherche dans une base de donnée d'images.

\subsection{Les moteurs de recherche d'images en ligne}

Il existe deux types généraux de moteurs de recherche d'images en ligne à
l'heure actuelle : ceux proposant la recherche dans une base d'images gérée
par l'hébergeur des images et se basant généralement sur des systèmes de tags,
et ceux proposant une recherche sur l'intégralité des images présentes sur le
web, se basant sur le contexte textuel des images.

Les moteurs cherchant à extraire du texte entourant les images (Google Images,
Yahoo, Exalead) pour effectuer ensuite de classiques requêtes textuelles sur
ceux-ci fournissent des résultats de qualité variable, pour de nombreuses
raisons. La première est que la requête textuelle peut avoir de très nombreux
sens. De plus, elle ne permet aucunement de rechercher un style d'image, ou
d'indiquer au moteur de recherche que telle image correspond ou non à notre
recherche.

\begin{figure}[h]
  \centering
  \includegraphics[height=5truecm]{figures/etat-de-l-art/google-images.png}
  \caption{Résultat d'une recherche d'images Google}
\end{figure}

Les moteurs se basant sur des classifications manuelles par tags des images
qu'ils hébergent (Flickr, Picasa Web) s'appuient eux aussi sur la présence
d'une vérité terrain sous forme textuelle caractérisant chacune des images de
la base. Néanmoins, qualifier l'intégralité de la base de données est très
coûteux en temps, et là aussi la sensibilité aux choix linguistiques est très
élevée : problèmes d'orthographe, de synonymie, d'estimation du sujet de
l'image sont nombreux.

\subsection{La recherche d'images basée sur le contenu}

L’exploitation des informations contenues dans l’image même, ses couleurs, ses
formes, ses textures, est un domaine de recherche très actif, et les
chercheurs en recherche d’images basée sur leur contenu (CBIR, Content Based
Image Retrieval) ont proposé de nombreux algorithmes permettant d’effectuer
des requêtes d’intérêt basées généralement sur la comparaison entre une image
“requête” et les images de la base de données pour afficher la liste de celles
qui lui sont ressemblantes, ou bien sur la comparaison entre un dessin fait
par l’utilisateur et les images de la base de données. Dans les deux cas, cela
consiste à faire une requête par l'exemple. Des prototypes de tels systèmes
sont déjà accessibles en ligne \cite{airliners,cires,retrievr}.

\begin{figure}[h]
  \centering
  \includegraphics[height=5truecm]{figures/etat-de-l-art/retrievr.png}
  \caption{Résultat d'une recherche d'images sur retrievr \cite{retrievr}}
\end{figure}

\subsection{Retour de pertinence}
\label{subsec:exploring_continuous_observational_data}

D'autres moteurs en développement \cite{FIRE,FIRE2} permettent
de filtrer les résultats entre images pertinentes ou non. Ainsi, à chaque
étape, le moteur raffine la recherche en proposant d'avantage d'images
similaires à celles classifiées comme pertinentes, et éloignées de celles qui
ne le sont pas.

\begin{figure}[h]
  \centering
  \includegraphics[height=5truecm]{figures/etat-de-l-art/fire.png}
  \caption{Résultat d'une recherche d'images sur FIRE \cite{FIRE}}
\end{figure}

\subsection{Exploration d'une base d'images}

Néanmoins, ces outils ne permettent généralement que de faire des recherches
dans la base de données, et pas d'explorer celle-ci. Pourtant, de nombreuses
recherches sont exploratoires : dès lors qu'on ne sait pas précisément ce qui
se trouve dans la base, et qu'on ne sait pas précisément quel contenu, quelle
apparence et quel style d'image l'on souhaite, il est très difficile de
formuler une requête convenable. DRIDE, reprenant de la recherche basée sur le
contenu les possibilités de relier des images visuellement proches, et du
retour de pertinence la possibilité d'effectuer une recherche itérative
spécifiant à chaque étape images intéressantes et images à exclure, cherche à
fournir une meilleure vue d'ensemble de la base de données.

\section{Solution proposée}
\label{sec:solution_apportee}

Le projet DRIDE vise à résoudre de façon plus efficace que les outils
actuellement existants le problème de l'exploration et de la recherche dans
une base de données d'image contenant (trop) peu d'informations textuelles sur
les images, c'est à dire pour laquelle on ne connaît pas la vérité terrain.
Nous partons pour cela de deux prémisses : que l'exploration d'une base de
données est la plus efficace lorsque les images sont arrangées par une notion
de proximité sémantique telle que ressentie par l'utilisateur, d'une part, et
d'autre part que celle-ci est en grande partie caractérisée par des
informations bas niveau sur l'image aisées à obtenir à partir de son contenu,
sans avoir à développer de complexes algorithmes de reconnaissance d'images ou
de formes.

Ces deux principes semblent raisonnables car les notions de couleur, de formes
locales et de texture sont effectivement, lorsque mises ensemble,
caractéristiques d'une image.

% TODO : back up this claim !

Il devient donc nécessaire tout d'abord d'extraire ces caractéristiques bas
niveau de l'image, puis de donner accès à celles-ci à l'utilisateur. On
constate rapidement qu'obtenir une information à propos du voisinage de chaque
point de l'image fournit généralement une très grande masse d'informations,
une représentation multidimensionnelle dans laquelle l'utilisateur ne pourra
naviguer aisément. De plus, la base de données elle-même n'a pas
nécessairement besoin de toute cette information pour être correctement étalée
dans l'espace, et ses variations adéquatement exhibées. C'est pourquoi dans un
second temps nous cherchons à effectuer une réduction de la dimension de
l'ensemble des données, pour, tout en conservant les voisinages de points,
obtenir une représentation dont la dimension correspond à la dimension
intrinsèque des données. Ainsi, si les données d'entrée sont réparties sur une
surface topologiquement homéomorphe à un hyperplan de dimension $d$ plongé
dans un espace de dimension $D > d$, alors les algorithmes de réduction
seraient chargés de réduire la dimension des données à la dimension $d$.

\subsection{Extraction de caractéristiques}

L'extraction de caractéristiques consiste à transformer la représentation sous
forme de pixels de l'image en une représentation sous forme d'un point dans un
espace multidimensionnel où chaque dimension correspond à une caractéristique
locale extraite de l'image. Les caractéristiques extraites sont tout
simplement des features de couleurs, de formes et de textures exprimant les
aspects bas niveau de l'image. Nous considérons qu'ils correspondent bien aux
aspects phénoménologiques ressentis par l'utilisateur, et que la proximité
dans l'espace des caractéristiques correspond bien à une proximité visuelle
des images.

De nombreux algorithmes existent pour faire de l'extraction de
caractéristiques. Ceux-ci n'ont pas été approfondis jusqu'ici dans le projet
DRIDE, mais l'extraction d'histogrammes de couleur, de filtres de Gabor
\cite{Gabor} pour les formes, et des filtres de textures tels que les filtres
de Hermite \cite{Hermite}.

\subsection{Réduction de dimensionnalité}

Une fois ces caractéristiques extraites, il est nécessaire de réduire la
dimension des données, afin d'une part de supprimer les dimensions ne
contenant pas d'information mais seulement du bruit, et ensuite afin d'obtenir
une représentation dépliée d'éventuelles surfaces complexes, permettant à
l'utilisateur de naviguer dans un nombre réduit de dimensions.

Les algorithmes de réduction de dimensionnalité sont nombreux \cite{dimreduc},
et le projet DRIDE a cherché à comparer d'une part leurs performances
relatives (consommation mémoire, temps de calcul), mais aussi leur capacité à
déplier des surfaces complexes, ou à conserver les proximités entre points
dans un voisinage :

\begin{figure}[h]
  \centering
    \includegraphics[width=7truecm]{figures/diffusionmaps.png}
    \includegraphics[width=7truecm]{figures/mds.png}
  \caption{Réductions de dimension sur le rouleau suisse (Diffusion maps à gauche, MDS à droite)}
  \label{fig:reduction_dimensionnalite}
\end{figure}

Les algorithmes les plus intéressants de ce point de vue sont Isomap et MDS,
pour leurs performances et la conservation des distances entre points voisins
dans l'espace de haute dimension. Il apparaît comme nécessaire de continuer
les expérimentations cette fois avec de vraies images afin d'être capables de
déterminer quel algorithme est le plus efficace pour obtenir une
représentation de basse dimensionnalité la plus exploitable par l'utilisateur.

\subsection{Transitions de dimensions animées}

Une fois une représentation de dimension plus basse, correspondant à la
dimension intrinsèque des données d'entrée, obtenue, il est généralement
nécessaire de donner à l'utilisateur un moyen de naviguer dans un espace de
dimension supérieure à 3, qui est la limite qu'une interface traditionnelle
permet de manipuler. C'est là que les transitions animées entre dimensions
entrent en jeu, afin de permettre à l'utilisateur de substituer des dimensions
nouvelles aux dimensions affichées de façon continue, afin de pouvoir à tout
instant suivre l'évolution de la position relative des points.

\begin{figure}[h]
  \centering
    \includegraphics[width=3.5truecm]{figures/anim-1.png}
    \includegraphics[width=3.5truecm]{figures/anim-2.png}
    \includegraphics[width=3.5truecm]{figures/anim-3.png}
    \includegraphics[width=3.5truecm]{figures/anim-4.png}
  \caption{Transition animée d'une représentation d'un rouleau suisse en 4 dimensions}
  \label{fig:transition_animee}
\end{figure}

\subsection{Architecture d'ensemble}

L'architecture d'ensemble est donc constituée de trois phases. Une phase
d'extraction d'une représentation de dimension élevée des données, puis une
réduction de ces données en un espace aisément manipulable, et enfin la
manipulation dans cet espace d'une vue des données permettant d'explorer les
rapports de proximité entre images.

\begin{figure}[h]
  \centering
    \includegraphics[width=15truecm]{figures/architecture.pdf}
  \caption{Architecture de DRIDE}
  \label{fig:architecture}
\end{figure}

Chaque étape s'appuie sur un composant indépendant, aisément réutilisable dans
d'autres projets. Le plus intéressant de ce point de vue est le composant
\verb|OpenGLDataViewer|, qui est comme son nom l'indique un visualiseur de
données OpenGL qui est capable d'afficher les positions de points dans un
espace multi dimensionnel et d'effecteur des transitions animées entre
dimensions, le tout écrit en python.

Les composants de réduction de dimensionnalité pourraient cependant être
utiles pour d'autres types d'applications, et sont à aussi aisément
réutilisables dans une solution développée en ou pouvant intégrer du python.
Il prend tout simplement en entrée la liste des coordonnées des points dans
l'espace de haute dimension, et la dimension cible, et fournit en sortie les
nouvelles coordonnées des points.

\section{Choix techniques et architecturaux}
\label{sec:choix_techniques_et_architecturaux}

La version de DRIDE qui a été développée pour l'instant est une version
simplifiée de l'ensemble de ce qui serait nécessaire pour permettre une
véritable analyse exploratoire d'une base d'images réelle, afin de permettre
en particulier d'expérimenter avec les différents algorithmes de réduction de
données, et d'expérimenter l'interface de manipulation des dimensions.

Le projet a été développé en python, en profitant des nombreuses librairies
disponibles :

\begin{itemize}
  \item \verb|numpy| pour les calculs numériques et matriciels ;
  \item \verb|pyopengl| pour la gestion de l'interface 3D ;
  \item \verb|PIL| pour les manipulations d'images ;
  \item \verb|pyui| pour l'interface utilisateur ;
  \item \verb|psyco| pour la compilation du code à la volée ;
  \item \verb|scikits.ann| pour le calcul de graphe des plus proches voisins ;
  \item \verb|hcluster|, \verb|pysomap| pour l'implémentation efficace des
        algorithmes de réduction.
\end{itemize}

La rapidité des développements, et la facilité d'adaptation de code existant
(code matlab des algorithmes de réduction par exemple) ont justifié ces choix.
De plus, le projet est directement multi-plateformes, aux procédures
d'installation des différents modules près. Enfin, comme démontré par
l'utilisation des libraries \verb|hcluster| et \verb|pysomap|, les portions
moins performantes du code et très gourmandes en ressources de calculs (les
algorithmes de réduction et l'extraction de caractéristiques) pourront être
aisément déportées dans des libraries ad-hoc compilées, sans modification
majeure de l'architecture du système.

\section{Fonctionnement}
\label{sec:fonctionnement}

DRIDE est un outil en ligne de commande permettant d'explorer un ensemble de
données générées automatiquement, ou obtenues à partir d'une liste d'images,
après avoir réduit la dimensionnalité de la matrice des données. Des
instructions d'installation sont disponibles sur le site {\em Google Code} du
projet \cite{DRIDE}. Pour obtenir des instructions lors de l'exécution, il
suffit d'exécuter la commande suivante :

\begin{lstlisting}
  DRIDE.py --help
\end{lstlisting}

\subsection{Généralités}

Il est possible d'obtenir de le numéro de version de l'application DRIDE en
cours d'utilisation avec l'option \verb|--version|. Il est possible d'afficher
des informations additionnelles concernant l'exécution de l'application en
ajoutant l'option \verb|--verbose|.

\subsection{Données en entrée}

Il faut tout d'abord fournir à DRIDE des données en entrée. Ces données sont
pour l'instant majoritairement automatiquement générées, afin par exemple
d'étudier l'efficacité des algorithmes de réduction sur un rouleau suisse
bruité. Le premier paramètre à fournir est donc le nom du générateur à
utiliser, avec l'option \verb|--generator=|. Pour les générateurs Il est
ensuite possible de spécifier le nombre de points de données à générer avec
\verb|-n|, un paramètre optionnel pour chaque générateur permettant d'altérer
l'aspect des données générées (rayon du rouleau suisse par exemple),
\verb|-p|, la quantité de bruit à ajouter aux données, \verb|-b|, et enfin la
dimension dans lesquelles l'ensemble de données d'entrée sera plongé,
\verb|-d|.

Les valeurs possibles pour l'option \verb|--generator| sont :

\begin{lstlisting}
['Gaussian', 'SwissRoll', '4DSwissRoll', 'SwissHole', 'CornerPlanes',
  'ToroidalHelix', '3DClusters', 'FromImages']
\end{lstlisting}

Pour l'option \verb|FromImages|, il n'est pas possible de spécifier la liste
des images à charger en ligne de commande. Le fichier
\verb|demo/FromImages.py| présente un exemple d'usage.

\subsection{Réduction de dimensionnalité}

Une fois les données d'entrée spécifiées, il faut ensuite réduire la
dimensionnalité des données. Il faut pour cela spécifier un algorithme de
réduction avec l'option \verb|--reducer=|. Les valeurs possibles pour l'option
\verb|--reducer| sont :

\begin{lstlisting}
['None', 'PCA', 'Isomap', 'DiffusionMaps', 'MDS']
\end{lstlisting}

Certains de ces algorithmes se basent sur un nombre de voisins pour construire
un graphe de distances, et ce paramètre est spécifié par l'intermédiaire de
l'option \verb|-k|. Enfin, il faut spécifier la dimension cible, correspondant
à la dimension intrinsèque de l'ensemble de données d'entrée, qui n'est pour
l'instant pas calculable directement dans DRIDE. Ce paramètre est spécifié
grâce à l'option \verb|-o|. Le fichier \verb|octave/README| décrit les
méthodes Matlab proposées pour déterminer de façon automatique la dimension
d'un ensemble de données.

% TODO : parler de dimension intrinsèque

\subsection{Interface de visualisation}

Une fois la réduction effectuée, les données sont affichées dans une interface
3D permettant de naviguer dans l'espace des données affiché, et aussi
d'effectuer des transitions animées entre jeux de dimensions. Pour naviguer en
trois dimensions, le clic gauche permet d'effectuer des rotations, le clic
droit permet d'effectuer des translations dans le plan de projection, et il
est possible de zoomer en maintenant la touche {\em z} enfoncée. La touche
{\em h} permet d'afficher une aide sur les autres commandes disponibles.

La fenêtre de gestion des dimensions et de leur animation permet de choisir
trois dimensions de départ et trois dimensions d'arrivée, et d'effectuer une
transition animée entre ces jeux de dimensions. Il est possible d'interrompre
une animation pendant son exécution, ce qui est matérialisé par la barre de
progression. L'interpolation entre les deux jeux de dimensions est linéaire
suivant chaque axe sur lequel une nouvelle dimension est substituée à une
dimension affichée.

Les couleurs dans l'interface correspondent aux classes spécifiée en entrée de
l'outil de visualisation. Elles permettent de vérifier que les proximités
entre données réduites correspondent bien aux proximités entre points dans les
données d'entrée des algorithmes de réduction. Deux modes de visualisation
sont disponibles, avec graphe de voisinage ou non. L'affichage de celui-ci
permet de révéler les raccourcis entre couches distinctes de la surface
représentée par les points en entrée, ou de mettre en valuer des goulets
d'étranglement par lesquels de nombreux chemins passent, déformant les
résultats des algorithmes de réduction se basant sur ces graphes pour baisser
la dimension de l'ensemble des données.

\section{Evolutions}

Plusieurs évolutions sont possibles pour le projet, dont les développements
sont loin d'être finalisés. La lacune la plus visible à l'heure actuelle est
le manque d'affichage des images elles-mêmes à côté des points dans
l'interface. Néanmoins, à plus long terme, deux questions principales se
posent : comment l'utilisateur accède-t-il à l'outil, et comment effectue-t-il
de façon concrète une recherche d'images ou une exploration de la base de
données.

\subsection{Plate-forme web}

Tout d'abord, la meilleure cible de déploiement semble être le monde du web,
ce qui amènerait un lot de contraintes nouvelles sur le projet, en particulier
en termes de capacité de visualisation : il faudrait se rabattre sur une
interface 2D, et s'adapter aux contraintes client-serveur que présente
l'Internet. Cependant, cela semble être la cible la plus prometteuse : les
moteurs de recherche sont le plus utiles pour accéder à des données qu'on n'a
pas encore en sa possession, et qui se trouvent donc disséminées sur la toile
ou rassemblées dans une base de données (plus ou moins) thématique.

Une telle plate-forme permettrait malgré tout des animations pour effectuer des
transitions entre dimensions affichées, à condition d'avoir une représentation
multi-échelles des données permettant de limiter dans une vue le nombre
d'images et d'informations à transmettre au client. Les principes exposés ici
d'extraction de caractéristiques et de réduction de dimension, pouvant être
faits en amont de la visualisation elle-même, seraient cependant parfaitement
parallélisables, et ne ralentissant pas la visualisation qui nécessite une
interactivité forte du système, ne requerront pas de modification profonde de
ce pan du système.

\subsection{Requêtes d'intérêt}

Les méthodes d'exploration présentées dans le projet jusqu'ici sont adaptées
pour se faire une idée du contenu de la base, ou l'explorer sans but précis,
mais dès lors qu'on souhaite trouver une image en particulier, il serait utile
que les animations, changements de dimensions ou de projection, soient
effectués de façon automatique par le système en fonction des retours de
l'utilisateur. Celui-ci effectuerait donc des requêtes d'intérêt, spécifiant
les images qui l'intéressent et celles qui ne l'intéressent pas, et le système
changerait simplement la vue (dimensions affichées, base de projection, et
niveau de zoom) afin d'écarter les images invalides et de mettre au centre de
la vue des images proches de celles indiquées comme étant valides. Ainsi, les
requêtes d'intérêt définiraient simplement une matrice de projection des
données, et ne nécessiteraient pas de recalculer la vue d'ensemble de la base
de données. Ceci pourrait donc être fait sans difficulté en temps réel.

Ainsi, en regroupant ces deux points, le schéma architectural du système
complet ressemblerait à la Figure~\ref{fig:evolutions}.

\begin{figure}[h]
  \centering
    \includegraphics[width=17truecm]{figures/evolutions.pdf}
  \caption{Schéma architectural de DRIDE pour le web}
  \label{fig:evolutions}
\end{figure}

Le moteur d’analyse sera chargé de transformer la base de données brutes en
une base de données contenant des informations de similarité entre images. Le
moteur d’exploration sera chargé de fournir un accès interactif à cette base
de données. Pour le moteur d’analyse, il faudra résoudre trois grandes
catégories de problèmes : l’extraction des caractéristiques des images, la
détermination de la dimensionnalité (qui d’un point de vue plus général serait
finalement le choix de l’algorithme de réduction de la dimensionnalité), et
enfin la réduction de la dimensionnalité à proprement parler. Les algorithmes
utilisés devront être capables de s’adapter à des données non spécialisées
(images très variées dans une même base de données). Il faudra aussi être
capables d’ajouter de façon incrémentale des images, sans être forcés à chaque
nouvelle image de refaire tous les calculs.

\section*{Conclusion}
\addcontentsline{toc}{section}{Conclusion}
\markboth{Conclusion}{}

En conclusion, le projet DRIDE a montré que l'approche consistant à extraire
des images des caractéristiques bas niveau, à réduire la dimension des données
obtenues afin de permettre à l'utilisateur de naviguer dans un espace de
dimension supérieure à trois grâce à des transitions animées entre dimensions
affichées était un concept innovant et prometteur. Néanmoins, les outils
développés jusqu'ici manquent encore de maturité, et il faudra choisir
rapidement une cible d'application entre le web et les logiciels de gestion
d'images personnels avant de continuer des développements pratiques à ce
niveau. Par ailleurs, des expérimentations avec des bases de données d'images
réelles seront nécessaires pour trancher définitivement en faveur
d'algorithmes d'extractions de caractéristiques et de réduction de
dimensionnalité.

\clearpage
\begin{thebibliography}{99}

\newcommand{\auth}{\textsc}

\bibitem{airliners} \auth{Wang J.Z. and Li J., PSU,}
SIMPLIcity,\\
{\em http://wang14.ist.psu.edu/cgi-bin/zwang/regionsearch\_show.cgi} (1999-2000),\\
{\em http://www.airliners.net/search/similarity\_search.php?photo\_id=1} (2005).

\bibitem{cires} \auth{Iqbal Q., CVRC, Univ. of Texas at Austin,}
CIRES: Content Based Image REtrieval System,\\
{\em http://amazon.ece.utexas.edu/~qasim/sample\_queries.htm} (2003-2007).

\bibitem{cires2} \auth{Iqbal Q. and Aggarwal J.K., CVRC, Univ. of Texas at Austin,}
Feature Integration, Multi-image Queries and Relevance Feedback in Image Retrieval,
{\em VISUAL} (2003), 467--474.

\bibitem{fast-mr-querying} \auth{Jacobs C., Finkelstein A. and Salesin D., Univ. of Washington,}
Fast Multiresolution Image Querying,
{\em SIGGRAPH} (1995), 277--286.

\bibitem{retrievr} \auth{Langreiter C.,}
retrievr,
{\em http://labs.systemone.at/retrievr/about} (2006).

\bibitem{FIRE} \auth{Deselaers T., Aachen Univ.,}
FIRE: Flexible Image Retrieval Engine,\\
{\em http://thomas.deselaers.de/FIRE} (2003-2008).

\bibitem{FIRE2} \auth{Deselaers T., Keysers D. and Ney H., Aachen Univ.,}
Features for Image Retrieval: An Experimental Comparison
{\em Information Retrieval}, (2008), {\bf 11}, 2, 77--107.

\bibitem{Gabor} \auth{Ibrahim A. and Azimi-Sadjadi M.R.,}
A fast learning algorithm for Gabor transformation
{\em IEEE Transactions on Image Processing}, (1996), {\bf 5}, 1, 171--175.

\bibitem{Hermite} \auth{Rivero-Moreno C.J. and Bres S.,}
Texture feature extraction and indexing by Hermite filters
{\em ICPR}, (2004), 684--687.

\bibitem{dimreduc} \auth{van der Maaten L.J.P., Maastricht Univ.,}
An Introduction to Dimensionality Reduction Using Matlab.
{\em Technical Report MICC}, (2007), 07-07.

\bibitem{DRIDE} \auth{Le Floch O., Burtschy B., Sahbi H., Schmitt F.,} \\
DRIDE: Dimensionality Reduction and Image Database Exploration, \\
{\em http://dride.googlecode.com/},
{\em http://code.google.com/p/dride/wiki/Installation}, (2008).

\end{thebibliography}

\listoffigures

\end{document}
